# -*- coding: utf-8 -*-

import random
import itertools

class Salesman:

    def __init__(self, matrix, nodos):
        self.matrix = matrix
        self.nodos = nodos

    def all_paths(self, nodos):
        for path in itertools.permutations(nodos):
            if path[0] < path[-1]:
                yield path
        
    def path_edges(self, path):
        return zip(path, path[1::])

    def all_edges(self):
        for edge in itertools.combinations(self.nodos, 2):
            yield edge
            yield (edge[1], edge[0])

    def edge_list_to_path(self, edge_list):
        path = []
        for edge in edge_list:
            path.append(edge[0])
            
        path.append(edge_list[-1][1])
        return path

    def path_distance(self, path):
        sum = 0;
        edges = self.path_edges(path)
        for edge in edges:
            sum += self.matrix[ edge[0] ][ edge[1] ]
        return sum    


    def display_path(self, path):
        return self.path_distance(path)

    def find_min_distance(self, paths):
        raise Exception("Subclase")

class BruteForceSalesman(Salesman):
    def find_min_distance(self):
        print "Fuerza bruta"

        all_paths = self.all_paths(self.nodos)
        min_distance= None
        min_paths = []
        path_count = 0
        for path in all_paths:
            print(path_count, path)
            path_count += 1
            dist = self.path_distance(path)
            if min_distance == None or dist < min_distance:
                min_paths = [path]
                min_distance = dist
            elif min_distance == dist:
                min_paths.append(path)
        print "Path: " + str(path_count) + ", ciudades " + str(len(min_paths[0]))
        return min_paths

class AntHillSalesman(Salesman):
    def __init__(self,habitacion_origen, matrix, nodos, ant_count, iterations, alfa, beta, q0, pheromone_control=0.1, distance_control=0.1, initial_pheromone=0.1):
        
        self.q0 = q0
        self.alfa = alfa
        self.beta = beta
        self.matrix = matrix
        self.nodos = nodos #rango
        
                
        self.habitacion_origen=habitacion_origen
        #self.habitacion_destino=habitacion_destino
        
        self.iterations = iterations
        self.ant_count = ant_count #numero de hormigas
        self.pheromone_control = pheromone_control
        self.distance_control = distance_control
        self.initial_pheromone = initial_pheromone
        
        self.evaporation = 0.01
        
        self.pheromone_map = {}
        self.initialize_pheromone_map()
        self.decay_pheromones()
        
    def initialize_pheromone_map(self):
        edges = self.all_edges()
        for edge in edges:
            self.pheromone_map[edge] = self.initial_pheromone #inicializa mapa de feromonas
        
    def find_min_distance(self):
        available_edges = self.all_edges() #todas las aristas

        # current best path found so far, there may be many paths with same cost
        best_paths = []
        best_distance = None
        
        for iteration in xrange(self.iterations):
            paths = []
            
            for ant_count in xrange(self.ant_count):
                path = self.ant_run(self.habitacion_origen)
                paths.append(path)
                distance = self.path_distance(path)
                
                if best_distance == None or distance < best_distance:
                    best_paths = [path]
                    best_distance = distance
                    
                elif distance == best_distance and not path in best_paths:
                    best_paths.append(path)
   
            #print "Iteration:", iteration, "best distance:", best_distance 
            self.decay_pheromones()
            for path in paths:
                self.leave_pheromones(path)
        return best_paths
        
    def ant_run(self,habitacion_origen):
        available_nodos = self.nodos[:]
        selected_edges = []
        #Seleccion nodo origen
        #current_city = habitacion_origen
        #Seleccion aleatoria
        current_city = random.sample(available_nodos, 1)[0]
        available_nodos.remove(current_city)
        
        while available_nodos:
            available_edges = [ (current_city, city) for city in available_nodos] 
            #print 'arista disponible: ', available_edges
            selected_edge = self.select_edge(available_edges) #Eleccion proxima arista
            current_city = selected_edge[1]
            available_nodos.remove(current_city)
            available_edges.remove(selected_edge)
            selected_edges.append(selected_edge)
            

        path = self.edge_list_to_path(selected_edges)
        return path
        
    def select_edge(self, available_edges): #Available edge, recibe las posibles aristas a seleccionar
        # compute probs for every edge
        all_edges_value = self.compute_all_edges_value(available_edges)
        
        
        edge_probs = {}
        for edge in available_edges:
                        
            edge_value= self.compute_edge_value(edge)

            prob = edge_value / all_edges_value
            edge_probs[edge] = prob
            

        # sort edges based on prob (highest first)
        sorted_edges = map(lambda x: x[1], 
                        sorted(
                        map(lambda edge: (1-edge_probs[edge], edge), available_edges)))

        # select random edge based on probs
        
        
        
        selection_value = random.random()
        
        if selection_value <= self.q0:
            return sorted_edges[-1]
            
        else:
            
            return edge
            
    
    def compute_edge_value(self, edge):
        distance = self.matrix[edge[0]][edge[1]]
        pheromone = self.pheromone_map[edge]
        
        # TODO does not use *_control
        # TODO this can be zero
        prob =  (pheromone**self.alfa)*(distance**self.beta)
        return prob

    def compute_all_edges_value(self, all_edges):
        prob = 0.0
        for edge in all_edges:
            prob += self.compute_edge_value(edge)
        return prob

    def leave_pheromones(self, path):
        delta = 1.0 / self.path_distance(path)
        
        for edge in self.path_edges(path):
            existing_pheromone = self.pheromone_map[edge]
            existing_pheromone += delta
            self.pheromone_map[edge] = existing_pheromone
            

    def decay_pheromones(self):
        pmap = self.pheromone_map
        mult = (1 - self.evaporation)
        for key in pmap:
            pheromone = pmap[key]            
            pheromone *= mult



def busca_minima_distancia(ruta_matriz, hormigas, colonias, alfa, beta,q0):
    nodo_count = 0
    matriz_archivo = open(ruta_matriz, 'r')
    matriz_de_ciudades = []
    distance_matrix = []
    linea_numero = []
    while (1):
      nodo_count+=1
      linea = matriz_archivo.readline()[:-1].split(',')
      
      if len(linea)<=1:
        break
      
      
      if len(linea) > 1:
        linea_numero =  [float(i) for i in linea]
        distance_matrix.append(linea_numero)
      
    
    
    import time
    random.seed(97531)
    
    
    nodos = range(nodo_count-1)
    
    salesman = AntHillSalesman(0,distance_matrix, nodos, hormigas, colonias, alfa, beta,q0)
    #salesman = BruteForceSalesman(distance_matrix, nodos)

    start = time.time()
    # all_paths = salesman.all_paths(nodos)
    paths = salesman.find_min_distance()
    end = time.time()
    
    tiempo = str(end - start)
    
    distancia = salesman.display_path(paths[0])
    return paths, tiempo, distancia
